# lowb三人组

'''
# 冒泡排序O(n2)
def bubble_sort(list):
    l = len(list)
    for i in range(l-1):
        for j in range(l-1-i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    print(list)
bubble_sort([1,5,4,2,4,7,342,5,22,45,2,0])
'''

'''
# 选择排序O(n2)
def select_sort(l):
    n = len(l)
    for i in range(n-1):
        min_index = i
        for x in range(i+1,n):
            if l[x] < l[min_index]:
                min_index = x
        if min_index != i:
            l[min_index],l[i] = l[i],l[min_index]


if __name__ == '__main__':
    alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
    select_sort(alist)
    print(alist)
'''

'''
# 插入排序
def insert_sort(li):
	n = len(li)
	for i in range(n-1):  # i是手里的牌
		tmp = li[i+1]  # tmp是刚抓的牌
		while i>=0 and li[i] > tmp: 
		# 刚抓的牌与手里的牌从右到左依次比较
			li[i+1] = li[i]
			i -= 1
		li[i+1] = tmp  # 抓的牌插入合适的位置
li = list(range(100))
import random
random.shuffle(li)
print(li)
insert_sort(li)
print(li)
'''


# nb三人组

'''
# 快速排序 O(nlogn)
def quick_sort(list):
    if list == []:
        return []
    else:
        a = list[0]
        left = [var for var in list if var<a]
        middle = [var for var in list if var==a]
        right = [var for var in list if var>a]
        return quick_sort(left)+middle+quick_sort(right)
print(quick_sort([1,5,4,2,4,7,342,5,22,45,2,0]))
'''

'''
# 堆排序O(nlogn)
# 调整
def sift(li, low, high):
	'''
	:param li: 列表
	:param low: 堆的根节点位置
	:param high: 堆的最后一个元素的位置
	:return:
	'''
	i = low  # 最开始i指向根节点,j是左孩子
	j = 2 * i + 1
	tmp = li[low] # 把堆顶保存起来用于交换
	while j <= high: # 只要j位置有数或者说下标在列表范围内
		if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有且比较大
			j = j + 1 # j指向右孩子（往右分支走）
		if li[j] > tmp:
			li[i] = li[j]  # 交换
			i  = j  # 往下一层
            j = 2 * i + 1 
		else:  # tmp更大，把tmp放到i的位置
			break
	li[i] = tmp # 把tmp合适的位置


def heap_sort(li):
	n = len(li)
	# 建堆
	for i in range((n-2)//2, -1, -1):
		# i表示建堆的时候调整部分的根的下标
		sift(li, i, n-1)
	# 挨个取数
	for i in range(n-1, -1, -1):
		# i指向当前堆的最后一个元素
		li[0], li[i] = li[i], li[0]  # 最后一个元素跟堆顶交换位置，接着向下调整
		sift(li, 0 , i-1) # i-1是最新的high

li = list(range(100))
import random
random.shuffle(li)
heap_sort(li)
print(li)

'''

"""topk问题：数组中取出前k大的数，
可以使用堆排序的方式来做
时间复杂度是O(mlogn) # (klogn)

def sift(li, low, high):
	'''
	:parma li: 需要调整的列表
	:parma low: 堆部分的根节点
	:parma high: 堆的最后一个元素
	:return:
	'''
	i = low  # 最开始i指向根节点
	j = 2 * i + 1  # 堆的叶子结点
	tmp = li[low]  # 临时保存堆顶元素用于交换 
	while j <= high: # 只要j没越界就一直比下去
		if j + 1 <= high and li[j] > li[j+1]: # 右孩子有且比左孩子大
			j = j +1 # j指向右孩子
		if li[j] < tmp: # 大于堆顶则将i移到j的位置
			li[i] = li[j]
			i = j  # 进入下一层
			j = 2 * i + 1
		else:
			break
	li[i] = tmp


def topk(li,k):
	heap = li[:k]
	print(heap)
	# 1.建堆
	for i in range((k-2)//2,-1,-1):
		sift(heap,i,k-1)
	# 2.遍历一次比较
	n = len(li)
	for i in range(k+1,n):
		if li[i] > heap[0]:
			heap[0] =  li[i]
			sift(heap,0,k-1)
	# 3.出数
	for i in range(k-1,-1,-1):
		heap[0],heap[i] = heap[i],heap[0]
		sift(heap,0,i-1)
	return heap

li = list(range(100))
import random
random.shuffle(li)
print(topk(li,10))
"""

# 归并排序
"""
def merge(li, low, mid, high):
	i = low  # 左边第一个
	j = mid + 1 # 右边第一个
	ltmp = []  # 新列表
	while i <= mid and j <= high:
		if li[i] < li[j]:
			ltmp.append(li[i])
			i += 1
		else:
			ltmp.append(li[j])
			j += 1
	# while执行完肯定有一边还有数据,将剩余的数据添加
	if i <= mid:
		ltmp.extend(li[i:mid+1])
	if j <= high:
		ltmp.extend(li[j:high+1])
	li[low:high+1] = ltmp  # 将新列表数据替换为li


def merge_sort(li,low,high):
	if low < high: # 至少有两个元素
		mid = (low + high) // 2
		merge_sort(li,low,mid) # 左部分递归
		merge_sort(li,mid+1,high) # 右部分递归
		merge(li,low,mid,high)  # 是先递归后合并，注意程序执行的顺序

li = list(range(100))
import random
random.shuffle(li)
print(li)
merge_sort(li,0,len(li)-1)
print(li)
"""

# 两个有序列表合并
"""
def merge(li1,li2,i,mid,j,high):
	ltmp = []
	while i <= mid and j <= high:
		if li1[i] < li2[j]:
			ltmp.append(li1[i])
			i+=1
		if li2[j] < li1[i]:
			ltmp.append(li2[j])
			j+=1
	# 将剩余的一边添加至新列表
	if i <= mid:
		ltmp.extend(li1[i:mid+1])
	else:
		ltmp.extend(li1[j:high+1])
	return ltmp

li1 = [1,5,7,9]
li2 = [2,3,4,8]
print(merge(li1,li2,0,len(li1)-1,0,len(li2)-1))
"""


# 希尔排序与基数排序

'''
# 希尔排序就是插入排序的变形，把1换成gap就行了
def insert_sort_gap(li,gap):
	n = len(li)
	for i in range(n-gap):
		tmp = li[i+gap]
		while i >= 0 and tmp < li[i]:
			li[i+gap] = li[i]
			i -= gap
		li[i+gap] = tmp

def shell_sort(li):
	gap = len(li)//2 # gap是数组长度的一半
	while gap >= 1:
		insert_sort_gap(li,gap)
		gap //= 2

import random
li = list(range(100))
random.shuffle(li)
shell_sort(li)
print(li)
'''

'''
# 基数排序
def radix_sort(li):
	n = len(str(max(li)))
	for i in range(n): # i代表个十百千万 依次分桶
		buckets = [[] for _ in range(10)] # 建捅
		for var in li: # 分桶
			digit = var // (10 ** i) % 10 # 根据i取余数
			buckets[digit].append(var) # 装桶
		li.clear()  # 不断的清空 
		for buc in buckets: # 将桶内数据依次添加到列表
			li.extend(buc)

import random
li = list(range(100))
random.shuffle(li)
radix_sort(li)
print(li)
'''

